package commonusealgorithm;

import java.util.Arrays;

/**
 * @Author PoX21s
 * @Date: 2021/10/31 19:06
 * @Version 1.0
 */

public class KPM {
    public static void main(String[] args) {
        String str1 = "ABCDABD";
        String str2 = "BCD ABCDAB ABCDABCDABDE";
        KPM kpm = new KPM();
        int[] next = kpm.getNext("ABCDABD");

        System.out.println(Arrays.toString(next));

        int index = kpm.searchString(str1, str2, next);

        System.out.println(index);
    }

    /*
    * 思路
    * - 根据目标字符串的前缀后缀比对建立索引表
    * - 字符搜索时，比对失败后，根据索引表移动
    * */
    public int searchString(String str1, String str2, int[] next){
        for (int i = 0,j = 0; i < str2.length(); i++) {
            while (j > 0 && str2.charAt(i) != str1.charAt(j)){
                j = next[j-1];
            }

            if (str2.charAt(i) == str1.charAt(j))
                j++;

            if (j == str1.length())
                return i - j + 1;
        }
        return -1;
    }

    public int[] getNext(String target){
       int[] next = new int[target.length()];

        for (int i = 1,j = 0; i < target.length(); i++) {
            while (j> 0 && target.charAt(i) != target.charAt(j)){
                j = next[j -1];
            }

            if (target.charAt(i) == target.charAt(j))
                j++;

            next[i] = j;
        }
       return next;
    }

}
